class Solution:
    def countSmaller(self, nums: list) -> list:
        if not nums:
            return []
        res_list = [0]
        mid_list = [nums[-1]]
        length, num = len(nums), nums[-1]
        for i in range(2, length+1):
            # 加了下面这个以后性能几乎没有改善
            # if nums[-i] == num:
            #     mid_res = mid_list.index(num)
            #     mid_list.insert(mid_res, num)
            #     res_list.append(mid_res)
            #     continue
            num = nums[-i]
            if num > mid_list[-1]:
                mid_list.append(num)
                res_list.append(i-1)
            # 其实这也没有太大改善
            elif num <= mid_list[0]:
                mid_list.insert(0, num)
                res_list.append(0)
            else:
                index, min_index, max_index = 0, -1, i - 1
                while max_index - min_index > 1:
                    if mid_list[index] >= num:
                        index, max_index = (min_index + index) // 2, index
                    else:
                        index, min_index = (max_index + index) // 2, index
                res_list.append(index+1)
                mid_list.insert(index+1, num)
        res_list.reverse()
        return res_list


class Solution2:
    def countSmaller(self, nums: list) -> list:
        """还是插在末尾最后反转快"""
        if not nums:
            return []
        res_list = [0]
        mid_list = [nums[-1]]
        lenght = len(nums)
        for i in range(2, lenght+1):
            num = nums[-i]
            if num > mid_list[-1]:
                mid_list.append(num)
                res_list.insert(0, i - 1)
            else:
                index, min_index, max_index = 0, -1, i - 1
                while max_index - min_index > 1:
                    if mid_list[index] >= num:
                        index, max_index = (min_index + index) // 2, index
                    else:
                        index, min_index = (max_index + index) // 2, index
                res_list.insert(0, index+1)
                mid_list.insert(index+1, num)
        return res_list


a = Solution()
print(a.countSmaller([5, 2, 6, 1]))
print(a.countSmaller([1]))
print(a.countSmaller([6, 1]))
print(a.countSmaller([1, 6]))
print(a.countSmaller([1, 1]))
